max_size = 100


class SString:
    def __init__(self):
        # 初始化一个空的串
        self.length = 0  # 串当前长度
        self.ch = [None] * max_size  # 最大长度为max_size的空间

    def str_assign(self, s):
        # 把串的值赋为s
        n = len(s)  # 求串s的长度
        if n > max_size - 1:  # 此处为max_size - 1因为0号单元弃用
            raise Exception('空间已满')
        else:
            self.length = 0  # 把串置为空
            while self.length < n:
                self.length += 1
                self.ch[self.length] = s[self.length - 1]
        return self

    def get_next_array(self, t):
        # 求模式串t的next函数值并存入数组next
        next_array = [0] * (t.length + 1)
        i = 1
        j = 0
        while i < t.length:
            if j == 0 or t.ch[i] == t.ch[j]:
                i += 1
                j += 1
                next_array[i] = j
            else:
                j = next_array[j]
        return next_array

    def index_kmp(self, s, t, pos, next_array):
        # 利用模式串t的next函数求t在主串s中第pos个字符之后的位置的KMP算法
        # 其中，t非空，1≤pos≤s.length
        i = pos
        j = 1
        while i <= s.length and j <= t.length:  # 两个串均未比较到串尾
            if j == 0 or s.ch[i] == t.ch[j]:
                i += 1
                j += 1  # 继续比较后继字符
            else:
                j = next_array[j]  # 模式串向右移动
        if j > t.length:
            return i - t.length  # 匹配成功
        else:
            return 0  # 匹配失败


if __name__ == '__main__':
    s, t = SString(), SString()
    ss = '123'
    tt = '23'
    pos = 1
    s.str_assign(ss)
    t.str_assign(tt)
    next_array = s.get_next_array(t)
    print('主串{0}和子串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), s.index_kmp(s, t, pos, next_array))
    ss = '123210'
    tt = '21'
    pos = 2
    s.str_assign(ss)
    t.str_assign(tt)
    next_array = s.get_next_array(t)
    print('主串{0}和子串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), s.index_kmp(s, t, pos, next_array))
    ss = '111111111'
    tt = '111'
    pos = 8
    s.str_assign(ss)
    t.str_assign(tt)
    next_array = s.get_next_array(t)
    print('主串{0}和子串{1}在第{2}个字符后首次匹配的位置为：'.format(ss, tt, pos), s.index_kmp(s, t, pos, next_array))